﻿// 4-23.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include "vector"
#include "list"
#include "queue"
using namespace std;

/// <summary>
/// 对一个向量某段两端有序分序列进行合并
/// </summary>
/// <param name="v"></param>
/// <param name="lo"></param>
/// <param name="mi"></param>
/// <param name="hi"></param>
void merge(vector<int>& v, int lo, int mi, int hi) {
    //现在始，A只在我的小脑袋里了，呜呜
    int lb = mi - lo;
    int* B = new int[lb];   //用数组好一些，而不用向量，向量也只是数组的包装罢了
    for (int i = 0; i < lb; i++) {  //从原来的向量里面，将前序列放入数组B中
        B[i] = v[lo + i];
    }
    
    //好了好了，现在C也只在我的脑袋里了，只有这样强写咯
    for (int i = lo, j = 0, k = mi; (j < lb) || (k < hi);) {
        if(j < lb && (!(k<hi) || B[j]<= v[k])) v[i++] = B[j++];
        if(k < hi && (!(j<lb) || v[k]< B[j])) v[i++] = v[k++];
    }
    //简化一下
    for (int i = lo, j = 0, k = mi; j < lb;) {
        if (k < hi && v[k] < B[j]) v[i++] = v[k++];
        if (k >= hi || B[j] <= v[k]) v[i++] = B[j++];
    }

    //增加代码行数，精简判断逻辑
    //如此的逻辑更直白一些，方便维护
     for(int i = lo, j = 0, k = mi; i < hi;){
         if(j < lb && k < hi){
             if(B[j] <= v[k]) v[i++] = B[j++];
             else v[i++] = v[k++];
         }
         else{
             if(lb <= j) return;
             else v[i++] = B[j++];
         }
     }
    delete[] B;


}

/// <summary>
/// 向量的排序
/// 使用二路归并思路来对向量进行排序
/// 二分归并，是一种思路，而非一种具体的算法
/// 一直一分为二，直至最小单个有序，
/// 此时每个序列，我均可保证其有序性，
/// 也正是因为每个序列的有序性，使得了接下来的二并一
/// 只需n，而非n平方
/// </summary>
/// <param name="v"></param>
void mergeSort(vector<int>& v, int lo, int hi) {  //一直都是左闭右开，如此之下，才得每序列之准确长度

    if (hi - lo < 2) return;
    int mi = (hi + lo) >> 1;
    mergeSort(v, lo, mi);
    mergeSort(v, mi, hi);
    merge(v, lo, mi, hi);

}


/// <summary>
/// 实现列表的二路归并，书中代码需要利用列表节点，但此处C++的列表与教材上实现不一致
/// 故先暂放
/// </summary>
/// <param name="li"></param>
/// <param name=""></param>
void mergeSort(list<int> li) {

}

/// <summary>
/// 应该对了，队列的二分归并
/// 只是用的变量太多，可能抓不住了
/// </summary>
/// <param name="q1"></param>
/// <param name="q2"></param>
void merge(queue<int>& q1, queue<int>& q2) {
    queue<int> q3;
    while (!q1.empty() || !q2.empty())
    {
        if (q1.front() <= q2.front()) {
            q3.push(q1.front());
            q1.pop();
        }
        else {
            q3.push(q2.front());
            q2.pop();
        }
    }
    q1 = q3;
}

/// <summary>
///
/// </summary>
/// <param name="q1"></param>
void mergeSort(queue<int>& q1) {
    int m = q1.size() / 2;
    int n = 0;
    queue<int> q2;
    for (int i = 0; i < m; i++) {
        n = q1.front();
        q2.push(n);
        q1.pop();
    }
    mergeSort(q1);
    mergeSort(q2);
    merge(q1, q2);
}



int main()
{
    std::cout << "Hello World!\n";
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
